package leetcode;

/*
思路：先判断两个数组的总大小。大小和如果是奇数，那么取（大小和）/2+1位置的数；如果大小和是偶数，那么取 (大小和/2-1 的数  + 大小和/2的数)/2

思考：

 */


import java.util.ArrayList;
import java.util.List;

public class Code4 {

    /*
        O(m+n)的解法，依次遍历数组1到数组2，如果到了中位数，那么直接返回中位数；如果还没有到中位数其中一个数组已经遍历结束，那么在另一个数组继续遍历得到中位数
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int length1 = nums1.length;
        int length2 = nums2.length;

        int allLength = length1 + length2;
        int midIndex = allLength / 2;
        int midPreIndex = midIndex - 1;
        int midNum = -1;
        int midPreNum = -1;


        boolean onlyMid = allLength % 2 == 1;
        int index1 = 0;
        int index2 = 0;
        int allIndex = 0;
        while (index1 < length1 && index2 < length2) {
            int curNums1 = nums1[index1];
            int curNums2 = nums2[index2];
            if (curNums1 <= curNums2) {
                if (allIndex == midPreIndex) {
                    midPreNum = curNums1;
                }
                if (allIndex == midIndex) {
                    midNum = curNums1;
                    return onlyMid ? midNum : (midNum + midPreNum) / 2.0;
                }
                index1++;
            } else {
                if (allIndex == midPreIndex) {
                    midPreNum = curNums2;
                }
                if (allIndex == midIndex) {
                    midNum = curNums2;
                    return onlyMid ? midNum : (midNum + midPreNum) / 2.0;
                }
                index2++;
            }
            allIndex++;
        }


        while (index1 < length1 && allIndex <= midIndex) {
            int curNums1 = nums1[index1];
            if (allIndex == midPreIndex) {
                midPreNum = curNums1;
            }
            if (allIndex == midIndex) {
                midNum = curNums1;
                break;
            }
            index1++;
            allIndex++;
        }

        while (index2 < length2 && allIndex <= midIndex) {
            int curNums2 = nums2[index2];
            if (allIndex == midPreIndex) {
                midPreNum = curNums2;
            }
            if (allIndex == midIndex) {
                midNum = curNums2;
                break;
            }
            index2++;
            allIndex++;
        }
        return onlyMid ? midNum : (midNum + midPreNum) / 2.0;
    }


    /*
      将取中位数转换为取第K小的数。
     */
    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
    }

    private static int getKth(int[] nums1, int start1, int end1, int[] num2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        if (len1 > len2) {
            //让 nums1 持续小于 num2,那么如果有数组空了，可以保证一直是nums1，这样后续处理较为简单
            return getKth(num2, start2, end2, nums1, start1, end1, k);
        }

        if (len1 == 0) {
            // 其中一个数据空了，那么取另一个数据的第k个即可
            return num2[start2 + k - 1];
        }

        if (k == 1) {
            return Math.min(num2[start2], nums1[start1]);
        }

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > num2[j]) {
            return getKth(nums1, start1, end1, num2, j + 1, end2, k - (j - start1 + 1));
        } else {
            return getKth(nums1, i + 1, end1, num2, start2, end2, k - (i - start1 + 1));
        }
    }

    /*
     中位数能够将一个数组分成长度相等的两个数组。
     利用这里特性，我们只要将两个数组最终分为长度相等的两个数组就好了。
     假设数组1的长度小于数组2，先将数组1划分为两半，分别为n和m，那么为了凑够两个相同数量的数组，n需要数组2的前半部，m需要数据2的后半部分。
     那么只要n 中的最大值 小于等于m中的最小值，那么中位数就得到了，必为其中一个或者两个数的平均值
      如果n中的最大值，大于m中的最小值，那么n就要减掉最大的数，把m中最小的数换到n中。划分原始数组的游标需要滑动。
     */
    public static double findMedianSortedArrays3(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) {
           return  findMedianSortedArrays3(nums2, nums1);
        }
        int iMin = 0;
        int iMax = m;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if (j != 0 && i != m && nums2[j - 1] > nums1[i]) {
                // 增加i
                iMin = i + 1;
            } else if (i != 0 && j != n && nums1[i - 1] > nums2[j]) {
                // 减小j
                iMax = i - 1;
            } else { // 达到要求，并且将边界条件列出来单独考虑
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = nums2[j - 1];
                } else if (j == 0) {
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                } // 奇数的话不需要考虑右半部分

                int minRight = 0;
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums2[j], nums1[i]);
                }

                return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果
            }
        }
        return 0.0;
    }


    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{}, new int[]{2, 3}));
    }


}
